\subsection{Übungsblatt 5 - Elliptische Kurven}

\subsubsection{Übung (i)}
\paragraph{Aufgabe}
Sei $(G, \circ)$ eine (beliebige) Gruppe, von der wir nur wissen, dass ihre Ordnung $|G|$ eine Primzahl ist.

Begründen Sie, dass $G$ zyklisch ist, d.h.\ dass es ein $g \in G$ gibt, so dass sich alle $h \in G$ schreiben lassen als $h = \underbrace{g \circ \ldots \circ g}_{x-\text{mal}}$ für ein $x \in \Z$. (\emph{Hinweis:} welche Ordnungen können die Gruppenelemente haben?)

\paragraph{Lösung}
Die Gruppe $G$ ist genau dann zyklisch, wenn der Erzeuger $g$, alle Elemente von $G$ erzeugt. D.h., wenn $g^k$ für $1 \leq k \leq p$ alle Elemente von $G$ erzeugt. Dafür muss die Ordnung von $g$ gleich der Gruppenordnung von $G$ sein; $order_g = |G|$. 

Es ist bekannt, dass die Ordnung eines Elements immer ein Teiler der Gruppenordnung ist. Da nach Voraussetzung die Gruppenordnung eine Primzahl ist, haben die Elemente in $G$ die Ordnung $1$ (das neutrale Element) oder die Ordnung $p$ (alle anderen). Wenn man ein beliebiges, vom neutralen Element verschiedenes, Elemente aus $G$ nimmt, erzeugen dessen Potenzen die ganze Gruppe $G$ [Buchmann: S.35].

\subsubsection{Übung (ii)}
\paragraph{Aufgabe}
Wieviele Punkte hat die elliptische Kurve $y^2 = x^3 + x + 1$ über $GF(7)$? Ist die Punktgruppe zyklisch? Wenn ja, bestimmen Sie einen Erzeuger.

\paragraph{Lösung}
$y^2 \equiv x^3 + x + 1 \mod 7$
\begin{align*}
&\text{\textbf{x, y}}   & y^2 \mod 7 && x^3 + x + 1 \mod 7  \\
&0: & 0 && 1 \\
&1: & 1 && 3 \\
&2: & 4 && 4 \\
&3: & 2 && 3 \\
&4: & 2 && 6 \\
&5: & 4 && 5 \\
&6: & 1 && 6 \\
\end{align*}

\hspace*{1cm}$\Rightarrow$ Vergleicht man die Werte ergeben sich folgende Punkte: $\mathcal{O}$, (0,1), (0,6), (2,2), (2,5) \newline
\hspace*{1cm}$\Rightarrow$ $|E| = 5$ $\Rightarrow$ zyklisch, da prim \newline
\hspace*{1cm}$\Rightarrow$ Alle Punkte außer $\mathcal{O}$ sind Erzeuger. \newline

\newpage
\subsubsection{Übung (iii)}
\paragraph{Aufgabe}
Betrachten Sie die durch $p = 7, a = 3, b = 2$ definierte elliptische Kurve $E$. Welche Abschätzung für $|E|$ erhalten Sie mit dem Satz von Hasse? Bestimmen Sie dann alle Elemente von $E$ ($\mathcal{O}$ nicht vergessen!). Wie viele Elemente enthält die vom Punkt $(5,4)$ erzeugte Untergruppe? Wie viele die Untergruppe, die von $(0,3)$ erzeugt wird? Ist $E$ zyklisch?

\paragraph{Lösung}

a.) Satz von Hasse

\begin{align*}	
 p + 1 - 2 \sqrt{p} &\leq |E| \leq p + 1 + 2 \sqrt{p} \\
 7 + 1 - 2 \sqrt{7} &\leq |E| \leq 7 + 1 + 2 \sqrt{7} \\
 2,71 &\leq |E| \leq 13,3 \\
 3 &\leq |E| \leq 13
\end{align*}

b.) $y^2 \equiv x^3 + 3x + 2 \mod 7$

\begin{align*}
&\text{\textbf{x, y}}   & y^2 \mod 7 && x^3 + 3x + 2 \mod 7  \\
&0: & 0 && 2 \\
&1: & 1 && 6 \\
&2: & 4 && 2 \\
&3: & 2 && 3 \\
&4: & 2 && 1 \\
&5: & 4 && 2 \\
&6: & 1 && 5 \\
\end{align*}

\hspace*{1cm}$\Rightarrow$ Punkte: $\mathcal{O}$, (0,3), (0,4), (2,3), (2,4), (4,1), (4,6), (5,3), (5,4) \newline

c.) Allgemeine Formeln:

\begin{eqnarray*}
	x_3 = s^2 - x_1 - x_2 \mod p \nonumber \\
	y_3 = s(x_1 - x_3) - y_1 \mod p \nonumber \\
\end{eqnarray*}

\hspace*{1cm}mit

\begin{equation*}
	s = \left \{ 
		\begin{array}{rl} 
		\mbox{$\frac{y_2 - y_1}{x_2 - x_1} \mod p$}  &;\mbox{$P \neq Q$}\\
		\mbox{$\frac{3x_1^2 + a}{2y_1} \mod p$}  &;\mbox{$P = Q$}\\
		\end{array} \right.	
\end{equation*}

\hspace*{0.75cm}Untergruppe vom Punkt $P = (5,4)$:

\begin{align*}
	P &= (5,4) \\
	2P &= (5,4) + (5,4) = (5,3)\\
	3P &= P + 2P = (5,4) + (5,3) = \mathcal{O}\\
	4P &= 2P + 2P = (5,3) + (5,3) = (5,4)\\
		 &\vdots
\end{align*}

\hspace*{1cm}$\Rightarrow$ Punkte: $\mathcal{O}$, (5,4), (5,3) \newline

\newpage
d.) Untergruppe vom Punkt $P = (0,3)$:

\begin{align*}
	P &= (0,3) \\
	2P &= (0,3) + (0,3) = (2,3)\\
	3P &= 2P + P = (2,3) + (0,3) = (5,4)\\
	4P &= 2P + 2P = (2,3) + (2,3) = (4,6)\\
	5P &= 4P + P = (4,6) + (0,3) = (4,1)\\
	6P &= 3P + 3P = (5,4) + (5,4) = (5,3)\\
	7P &= 6P + P = (5,3) + (0,3) = (2,4)\\
	8P &= 4P + 4P = (4,6) + (4,6) = (0,4)\\
	9P &= 8P + P = (0,4) + (0,3) = \mathcal{O}\\
		 &\vdots
\end{align*}

\hspace*{1cm}$\Rightarrow$ Punkte: $\mathcal{O}$, (0,3), (2,3), (5,4), (4,6), (4,1), (5,3), (2,4), (0,4) \newline

d.) $E$ ist zyklisch, da der Punkt $(0,3)$ ein Erzeuger ist.
